package lc.q1_50;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * 给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
 *
 * k 是一个正整数，它的值小于或等于链表的长度。
 *
 * 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
 *
 *  
 *
 * 示例：
 *
 * 给你这个链表：1->2->3->4->5
 *
 * 当 k = 2 时，应当返回: 2->1->4->3->5
 *
 * 当 k = 3 时，应当返回: 3->2->1->4->5
 *
 *  
 *
 * 说明：
 *
 * 你的算法只能使用常数的额外空间。
 * 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
 *
 */
public class Q25 {
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }
    public static ListNode reverseKGroup(ListNode head, int k) {
        // 每k个节点翻转
        // 如何知道
        ListNode h = new ListNode(0);
        h.next = head;
        ListNode nHead = null;
        out:while (h != null) {
            ListNode tail = h;
            for (int i = 0; i < k; i++) {
                assert tail != null;
                tail = tail.next;
                if (tail ==  null && i < k -1) {
                    break out;
                }
            }
            ListNode l = revert(h, tail);
//            print(l);
            if (nHead == null) {
                nHead = l.next;
            }
            // 下面这个值如何赋值？
            h = l;
            for (int i = 0; i < k && h != null; i++) {
                h = h.next;
            }

        }
        return nHead;
    }

    /**
     * 翻转前k个节点的过程
     * @param h
     * @param k
     * @return
     */
    public static ListNode revert(ListNode n, ListNode tail) {
        if (tail == null) {
            return n;
        }
        // 再前面补充一个假的头节点
        ListNode h = n.next;
        while (n.next != tail) {
            ListNode temp = n.next;
            n.next = h.next;
            h.next = n.next.next;
            // 这个错了
            n.next.next=temp;
        }
        return n;
    }

    public static void main(String[] args) {
        String link = "1->2->3->4->5";
        final String[] split = link.split("->");
        ListNode node = null;
//        for (int i = split.length - 1; i >= 0; i--) {
//            ListNode n = new ListNode(Integer.parseInt(split[i]));
//            n.next = node;
//            node = n;
//        }
        final Random random = new Random();
        final int i = random.nextInt(30);
        List<Integer> nums = new ArrayList<>();
        for (int j = 0; j < i; j++) {
            nums.add(j);
        }
        for (int j = 0; j < i; j++) {
            final int x = random.nextInt(nums.size());
            final Integer num = nums.get(x);
            nums.remove(x);
            ListNode n = new ListNode(num);
            n.next = node;
            node = n;
        }
        print(node);
        print(reverseKGroup(node, 3));
    }

    public static void print(ListNode node) {
        while (node != null) {
            System.out.print(node.val);
            node = node.next;
            if (node != null) {
                System.out.print("->");
            }
        }
        System.out.println();
    }

}


